package week_nine;

import java.util.*;

public class WordLadder_127 {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Map<String, Integer> distBegin = new HashMap<>();
        Map<String, Integer> distEnd = new HashMap<>();

        for (String word : wordList) {
            distBegin.put(word, (int) 1e9);
            distEnd.put(word, (int) 1e9);
        }
        if (!distBegin.containsKey(endWord)) return 0;

        distBegin.put(beginWord, 1);
        distEnd.put(endWord, 1);
        Queue<String> qBegin = new LinkedList<>();
        qBegin.offer(beginWord);
        Queue<String> qEnd = new LinkedList<>();
        qEnd.offer(endWord);

        while (!qBegin.isEmpty() || !qEnd.isEmpty()) {
            int res = expand(qBegin, distBegin, distEnd);
            if (res != -1) return res;
            res = expand(qEnd, distEnd, distBegin);
            if (res != -1) return res;
        }
        return 0;

    }

    private int expand(Queue<String> q, Map<String, Integer> dist, Map<String, Integer> distOther) {
        if (!q.isEmpty()) {
            String s = q.poll();
            int n = s.length();
            int depth = dist.get(s);
            for (int i = 0; i < n; i++) {
                for (char c = 'a'; c <= 'z'; c++) {
                    StringBuilder sb = new StringBuilder(s);
                    sb.setCharAt(i, c);
                    String newS = sb.toString();
                    if (dist.containsKey(newS)) {
                        if (dist.get(newS) > depth + 1) {
                            dist.put(newS, depth + 1);
                            q.offer(newS);
                            if (distOther.get(newS) != (int) 1e9) {
                                return depth + distOther.get(newS);
                            }
                        }
                    }
                }
            }
        }
        return -1;
    }
}
